package pers.qianyu.month_202101.date_20210116;

import pers.qianyu.util.model.*;

import java.util.*;

/**
 * 95. 不同的二叉搜索树 II
 * https://leetcode-cn.com/problems/unique-binary-search-trees-ii/
 *
 * @author mizzle rain
 * @date 2021年1月16日22:26:56
 */
public class GenerateTrees {
    public List<TreeNode> generateTrees(int n) {
        if (n <= 0) return new ArrayList<>();
        return dfs(1, n);
    }

    private List<TreeNode> dfs(int left, int right) {
        ArrayList<TreeNode> res = new ArrayList<>();
        if (left > right) {
            res.add(null);
            return res;
        }
        for (int i = left; i <= right; i++) {
            List<TreeNode> leftNodes = dfs(left, i - 1);
            List<TreeNode> rightNodes = dfs(i + 1, right);
            for (TreeNode leftNode : leftNodes) {
                for (TreeNode rightNode : rightNodes) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    res.add(root);
                }
            }
        }
        return res;
    }
}
